package cn.zhaoyuening.algorithms.heap;

import java.util.Arrays;

/**
 * Created by Buynow on 2017/7/30.
 */
public class Heap {
    public static int[] buildHeap(int[] heap,int heapSize) {
        int lastParentIndex = parentIndex(heapSize-1);
        if (lastParentIndex<=0){
            return heap;
        }
        for (int i=lastParentIndex;i>=0;i--) {
            min_heapify(heap,heapSize,i);
        }
        return heap;
    }

    public static void min_heapify(int[] heap,int heapSize,int index) {
        int leftIndex = leftIndex(index);
        int rightIndex = rightIndex(index);
        int minValueIndex = index;
        if (leftIndex < heapSize && heap[leftIndex] < heap[minValueIndex]) {
            minValueIndex = leftIndex;
        }

        if (rightIndex < heapSize && heap[rightIndex] < heap[minValueIndex]) {
            minValueIndex = rightIndex;
        }

        if (minValueIndex == index) {
            return;
        }
        exchange(heap, index, minValueIndex);
        min_heapify(heap,heapSize,minValueIndex);
    }

    public static void heap_sort(int[] heap,int heapSize,boolean isMinHeap) {
        if (!isMinHeap) {
            buildHeap(heap, heapSize);
        }

        for (int i=heapSize-1;i>0;i--) {
            exchange(heap,0,i);
            heapSize--;
            min_heapify(heap,heapSize,0);
        }
    }

    public static int leftIndex(int i) {
        return i*2+1;
    }

    public static int rightIndex(int i) {
        return i*2+2;
    }

    public static int parentIndex(int i) {
        if (i == 0) {
            return -1;
        }
        return ((i + 1) / 2)-1;
    }

    public static void exchange(int[] heap, int indexA, int indexB) {
        int tmp = heap[indexA];
        heap[indexA] = heap[indexB];
        heap[indexB] = tmp;
    }

    public static void main(String[] args) {
        int[] heap = new int[]{8, 5, 2, 10, 3, 7, 1, 4, 6};
        buildHeap(heap, heap.length);
        System.out.println(Arrays.toString(heap));
        heap_sort(heap,heap.length,true);
        System.out.println(Arrays.toString(heap));
    }
}
